#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * @brief The Solution class 2070. 每一个查询的最大美丽值
 */
class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        // 升序排序
        std::sort(items.begin(), items.end());

        // 让items中每个价格的美丽值最大
        int n = items.size();
        for(int i = 1; i< n;i++)
        {
            items[i][1] = std::max(items[i][1],items[i-1][1]);
        }

        vector<int> answer(queries.size(),0);
        for(int i=0;i<answer.size();i++)
        {
            answer[i] = query(items, queries[i]);
        }

        return answer;
    }

    int query(const vector<vector<int>>& items, int value)
    {
        int l=0,r=items.size();

        while(l<r)
        {
            int mid = l + (r-l)/2;

            if(items[mid][0] > value)
            {
                r = mid;
            } else
            {
                l = mid+1;
            }
        }

        if(l == 0)
        {
            return 0;
        }


        return items[l-1][1];
    }
};

//vector<int> getList(int price,int beauty)
//{
//    vector<int> list(2);
//    list[0] = price;
//    list[1] = beauty;
//    return list;
//}

//int main()
//{
//    cout << "Hello World!" << endl;
//    Solution solution;
////    [[1,2],[3,2],[2,4],[5,6],[3,5]]
////    [1,2,3,4,5,6]

//    vector<vector<int>> items;
//    items.push_back(getList(1,2));
//    items.push_back(getList(3,2));
//    items.push_back(getList(2,4));
//    items.push_back(getList(5,6));
//    items.push_back(getList(3,5));
//    vector<int> queries;
//    queries.push_back(1);
//    queries.push_back(2);
//    queries.push_back(3);
//    queries.push_back(4);
//    queries.push_back(5);
//    queries.push_back(6);
//    vector<int> ret = solution.maximumBeauty(items,queries);
//    cout << "End" << ret.size() << endl;
//}
